\textbf{\Huge Problems}
%----------------------------------------------------------------------------------------
% Problem 1
%----------------------------------------------------------------------------------------
\section{Let A = \{a, b, c, d\}. Give an example (with justification) of a relation R on A that has none of the following properties: reflexive, symmetric, transitive.}
R = {(a,a),(a,b),(b,c)}.\\
It is not reflexive as it does not contain: (b,b),(c,c),(d,d).\\
It is not symmetric because it does not contain: (b,a), (c,b).\\
It is not transitive because it does not contain: (a,c) although it contains the valid steps to get to (a,c).
\newpage

%----------------------------------------------------------------------------------------
% Problem 2
%----------------------------------------------------------------------------------------
\section{A relation R is defined on $\mathbb{Z}$ by aRb if $|a-b|\leq 2$. Which of the properties reflexive, symmetric and transitive does the relation R possess? Justify your answers.}
We start by checking if it is reflexive:\\
\begin{equation}
aRa = |a-a|\leq 2 = |0|\leq 2 = True
\end{equation}
Next we check if it is symmetric:
\begin{equation}
aRb = |a-b|\leq 2
\end{equation}
\begin{equation}
bRa = |b-a|\leq 2
\end{equation}
Since we know that $|a-b| \equiv |b-a|$, we know that it is symmetric.\\
Lastly we check if it is transitive:
\begin{equation}
aRb \wedge bRc => aRc
\end{equation}
We provide a counterexample:\\
Let a = 0, b = 1, c = 3.
$aRb = |0-1|=1 \leq 2$ and $bRc = |1-3|=2 \leq 2$ implies $aRc = |0-3|= 3 \leq 2$ which is false.\\
We can conclude and say that the relation aRb is reflexive and symmetric but not transitive. 
\newpage
%----------------------------------------------------------------------------------------
% Problem 3
%----------------------------------------------------------------------------------------
\section{Let A and B be sets with $|A|=|B|=4$.}
\begin{enumerate}[a.]
\item Prove or disprove: If R is a relation from A to B where $|R|=9$ and $R = R^{-1}$, then $A=B$.
\item Show that by making a small change in the statement in (a), a different response to the resulting statement can be obtained.
\end{enumerate}
\textbf{a.}:\\
We will disporve the statement.\\
Let A = \{1, 3, 5, 7 \} and B = \{1, 3, 5, 9 \}.  $|A| = 4 = |B|$.\\
Let R = \{(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5)\}. $|R|=9$ and $R^{-1} = R$.\\
We see that A = B evaluates to be false as the fourth element in each is not equal.\includegraphics[scale=0.70]{billeder/xzibit}\\
\textbf{b.}:\\
If we let |R|= 10 and R = $R^{-1}$. We add $(7,7)$ to the relation. This means that A = \{1, 3, 5, 7\} and B = \{1, 3, 5, 7\}. Now A = B which is a different response as it is true.
\newpage
%----------------------------------------------------------------------------------------
% Problem 4
%----------------------------------------------------------------------------------------
\section{Let R be a relation defined on $\mathbb{Z}$ by aRb if $a^3 = b^3$. Show that R is an equivalence relation on $\mathbb{Z}$ and determine the distinct equivalence classes.}
We see if the relation is and equivalence relation by checking the individual relations:\\
\textbf{Reflexive:}\\
$aRa: a^3=a^3$, which is true\\ 
Hereby the relation is reflexive.\\
\textbf{Symmetrics:}\\
If$aRb: a^3=b^3$\\
then $bRa: b^3=b^3$\\
and hereby the relation is symmetric.\\
\textbf{Transitive:}\\
If $aRb: a^3=b^3$\\
and $bRc: b^3=c^3$\\
then $aRc: a^3=c^3$\\
and hereby the relation is transitive.\\
\\
The distinct equivalence classes are defined as classes or sets of number which are equal/equivalent. We know $a^3=b^3$ only holds if $a=b$. This means that there exists an equivalence class $[a]=\{a\},  \forall a \in \mathbb{Z}$

\newpage
%----------------------------------------------------------------------------------------
% Problem 5
%----------------------------------------------------------------------------------------
\section{Let $H = \{2^m : m\in \mathbb{Z}\}$. A relation R is defined on the set $\mathbb{Q}^{+}$ of positive rationals by aRb if $a/b\in H$.}
\begin{enumerate}[a.]
\item Show that R is an equivalence relation.
\item Describe the elements in the equivalence class [3].
\end{enumerate}
To show that R is an equivalence relation we will show that the relation is reflexive, symmetric and transitive.\\
\textbf{a:}\\
\textbf{Reflexive:}\\
$aRa: \frac{a}{a}=1$ which is in H thereby the relation is reflexive.\\
\textbf{Symmetric:}\\
$aRb: \frac{a}{b}$ where the relation is in H: $\frac{a}{b}=2^m$\\
$bRa: \frac{b}{a}$ here the relations is also in H: $\left(\frac{a}{b}\right)^{-1}=\left(2^m\right)^{-1}$ which is equal to $\frac{b}{a}=2^{-m}$\\
Hereby the relation is symmetric.\\
\textbf{Transitive:}\\
$aRb:\frac{a}{b}$ let this be in H by some m by $2^m$ which is in H\\
$bRc:\frac{b}{c}$ let this also be in H by some $m_2$ by $2^{m_2}$ which is in H\\
$aRc:\frac{a}{c}$ this can be shown as: $\frac{a}{b}*\frac{b}{c}=2^m*2^{m_2}$ which is equal to $\frac{a}{c}=2^{m+m_2}$\\
Therefore the relation is also transitive.\\
\textbf{b:}\\
So the equivalence class [3] is $\{a\vee b=3:\frac{a}{b}=2^m\}$. Since the relation is an equivalence relation i can choose whichever(a or b) i want so: $b=3,\frac{a}{3}=2^m$ and here we solve for a: $a=2^m*3$ so the equivalence class $[3]=\{2^m*3:m\in\mathbb{Z}\}$.
\newpage
%----------------------------------------------------------------------------------------
% Problem 6
%----------------------------------------------------------------------------------------
\section{Two parts:}
\begin{enumerate}[a.]
\item Prove that the intersection if two equivalence relations on a nonempty set is an equivalence relation.
\item Consider the equivalence relations $R_2$ and $R_3$ defined on $\mathbb{Z}$ by a$R_2$b if $a\equiv b(mod 2)$ and a$R_3$b if $a\equiv b(mod 3)$. By (a), $R_1=R_2\cap R_3$ is an equivalence relation on $\mathbb{Z}$. Determine the destinct equivalence classes in $R_1$.
\end{enumerate}
\textbf{a:}\\
Let A be a nonempty set.\\
Then let two equivalent relations be:\\
$R_1\subseteq $A$\times$A and $R_2\subseteq $A$\times$A\\
Here we know $R_3=R_1 \cap R_2$\\
We check for the reflexive property:\\
Then let a$\in$A where (a,a)$\in R_1 \cap$ (a,a)$\in R_2$ then (a,a)$\in R_3$ therefore $R_3$ must be reflexive.\\
Next we check for the symmetric property:\\
Let a,b$\in$A where (a,b),(b,a)$\in R_1 \cap$ (a,b),(b,a)$\in R_2$ then (a,b),(b,a)$\in R_3$ therefore $R_3$ must be symmetric.\\
Last we check for the transitive property:\\
Let a,b,c$\in$A where (a,b),(b,c),(a,c) $\in R_1 \cap$ (a,b),(b,c),(a,c)$\in R_2$ then (a,b),(b,c),(a,c) $\in R_3$ therefore $R_3$ must be transitive.\includegraphics[scale=0.70]{billeder/xzibit}\\
\textbf{b:}\\
We know the relation $R_2$ can be written as $2|(a-b)$ and the relation $R_3$ can be written as $3|(a-b)$. The relation $R_2$ is all even numbers which can be written as $2x$ where $x=(a-b)$. The relation $R_3$ is for all a and b of the form (a-b) is divisible by 3 which is equivalent to $3x$ where x is (a-b). The relation of the intersection of $R_2$ and $R_3$ must then be $3(2x)=6x\equiv a=b(mod(6))$ where $x=(a-b)$. So the intersection is all numbers which are divisible by 6.
When we have mod(6) we can have 6 possible outcomes of remainder, namely: 0,1,2,3,4,5. This can be written as 6 possible equivalence classes which will always give us the same outcome:
\begin{center}
$[0]=\{\forall x\in \mathbb{Z}:6x\}$ - This will always give 0 in remainder.\\
$[1]=\{\forall x\in \mathbb{Z}:6x+1\}$ - This will always give 1 in remainder.\\
$[2]=\{\forall x\in \mathbb{Z}:6x+2\}$ - This will always give 2 in remainder.\\
$[3]=\{\forall x\in \mathbb{Z}:6x+3\}$ - This will always give 3 in remainder.\\
$[4]=\{\forall x\in \mathbb{Z}:6x+4\}$ - This will always give 4 in remainder.\\
$[5]=\{\forall x\in \mathbb{Z}:6x+5\}$ - This will always give 5 in remainder.\\
\end{center}

\newpage
%----------------------------------------------------------------------------------------
% Problem 7
%----------------------------------------------------------------------------------------
\section{Let A = \{1,2,3\} and B = \{a,b,c,d\}. Give an example of a relation R from A to B containing exactly three elements such that R is not a function from A to B. Explain why R is not a function.}
For a relation to be a function it must only have one output per input (it must not split).\\
Therefore a relation which is not a function could be:\\
$R={(1,a),(1,b),(1,c)}$\\
\newpage
%----------------------------------------------------------------------------------------
% Problem 8
%----------------------------------------------------------------------------------------
\section{For a function f : A $\rightarrow$ B and subsets C and D of A and E and F of B, prove the following:}
\begin{enumerate}[a.]
\item $f(C \cup D) = f(C) \cup f(D)$
\item $f(C \cap D) \subseteq f(C) \cap f(D)$
\item $f(C) - f(D) \subseteq f(C-D)$
\item $f^{-1}(E \cup F) = f^{-1}(E) \cup f^{-1}(F)$
\item $f^{-1}(E \cap F) = f^{-1}(E) \cap f^{-1}(F)$
\item $f^{-1}(E - F) = f^{-1}(C) - f^{-1}(D)$
\end{enumerate}
For a., b. and c. x is in A and y is in B. For d., e. and f. x is in B and y is in A.\\
\textbf{a.}\\ So a function gives us some y for some x. The x is in the set consisting of the union of C and D so on the left side we get some y from the function. On the right side either C og D contains said x so we also get that y in the union of the two functions.\\
\textbf{b.}\\ The same as a. applies. We know that for some x we get a y. And this x must be in both C and D. On the other side both function gives this y for the x. And since both sets in the function returns y it must be in the intersection. Since it is subset or equal we can show it the other way around to actually show that it is equals. So in the intersection of f(C) and f(D) is a y. And since a function cannot return 2 outputs to one input both sets must contain the x which gives us the y. And since x is in both set it will be in the intersection and the function will return y.\\
So: $x\in C \ or\ x \in D$ f(x)=y and $y\in f(C)\ or\ f(D)$\\
\textbf{c.}\\
Let f(C) - f(D) equal some y. Let (C-D) = x then f(x) = y. This means that f(C) - f(D) is a subset or equal to f(C-D).\\
\textbf{d.}\\
So a function gives us some y for some x. The x is in the set consisting of the union of E and F so on the left side we get some y from the function. On the right side either E og F contains said x so we also get that y in the union of the two functions.\\
\textbf{e.}\\
The same as e. applies. We know that for some x we get y. And this x must be in both E and F. On the other side both function gives this y for the x. And since both sets in the function returns y it must be in the intersection. Since it is subset or equal we can show it the other way around to actually show that it is equals. So in the intersection of f(E) and f(F) is a y. And since a function cannot return 2 outputs to one input both sets must contain the x which gives us the y. And since y is in both set it will be in the intersection and the function will return y.\\
So: $x\in E \ or\ x \in F$ f(x)=y and $y\in f(E)\ or\ f(F)$\\
\textbf{f.}\\
Let (E-F) = x. $f^{-1}(x) = y$. We let $f^{-1}(E) - f^{-1}(F) = y$. This means that $f^{-1}(E-F) = f^{-1}(E) - f^{-1}(F)$.\\
\newpage
%----------------------------------------------------------------------------------------
% Problem 9
%----------------------------------------------------------------------------------------
\section{Prove that the function f : R $\rightarrow$ R defined by f(x) = 7x - 2 is bijective.}
For a function to be bijective it needs to be both "onto" and "one-to-one".\\
First we will show that the function is "one-to-one":\\
We will check that only one unique input gives one unique output. Assume two arbitrary number a and b. Then $f(a)=f(b)$ we insert a and b to the functions\\
$7a-2=7b-2$ add 2 to each side and divide by 7\\
$a=b$ Then a must be equal to b and we have that the function must be one to one.
We will see if it is "onto":\\
For a function to be "onto" we need to prove that for every interger y there is and integer x such that f(x)=y. Assume $x=\frac{y+2}{7}$ then $7(\frac{y+2}{7})-2=y$.\\
Therefore the function must be bijective.\includegraphics[scale=0.70]{billeder/xzibit}
\newpage
%----------------------------------------------------------------------------------------
% Problem 10
%----------------------------------------------------------------------------------------
\section{Prove or disprove the following:}
\begin{enumerate}[a.]
\item If two functions f : A $\rightarrow$ B and g : B $\rightarrow$ C are both bijective, then g $\circ$ f : A $\rightarrow$ C is bijective.
\item Let f : A $\rightarrow$ B and g : B $\rightarrow$ C be two functions. If g is onto, then g $\circ$ f : A $\rightarrow$ C is onto.
\item Let f : A $\rightarrow$ B and g : B $\rightarrow$ C be two functions. If g is one-to-one, then g $\circ$ f : A $\rightarrow$ C is one-to-one.
\item There exist functions f : A $\rightarrow$ B and g : B $\rightarrow$ C such that f is no onto and g $\circ$ f : A $\rightarrow$ C is onto.
\item There exist functions f : A $\rightarrow$ B and g : B $\rightarrow$ C such that f is no one-to-on and g $\circ$ f : A $\rightarrow$ C is one-to-one.
\end{enumerate}
\textbf{a.}\\
We start by checking for injection(one-to-one):\\
g $\circ$ f(x) = g $\circ$ f(y)\\
g(f(x)) = g(f(y))\\
Since g is injective(bijective).\\
f(x) = f(y)\\
and since f is injective(bijective).\\
x = y\\
Next up we check for surjection(onto):\\
Since we know that both g and f are surjective(onto):\\
Let $c \in C$. Since g is onto, there is an element $b \in B$ so that g(b) = c. Since f is onto, there is an element $a \in A$ so that f(a) = b. then:\\
\begin{equation}
g \circ f(a) = g(f(a)) = g(b) = c
\end{equation}
Since we started with an arbitrary element $c \in C$ and we found an element $a \in C$ which maps onto it, we have shown $g \circ f$ is surjective. \includegraphics[scale=0.70]{billeder/xzibit}\\
\textbf{b.}\\
Let $c \in C$. We know that g is onto so there is an element $b \in B$ so that g(b) = c. There exists an element $b \in B$ for which all elements $a \in A$, f(a) does not map onto b. $\exists b \in B, \forall	a \in A, f(a) \neq b$ so it is disproven.

\textbf{c.}\\
Let $c \in C$. We know that g is one-to-one so there are elements $a,b \in A$ for which g(a) = g(b). Since we do not know if f is one-to-one, there exists elements $a,b \in A$ for which $f(a) \neq f(b)$ so it is disproven.

\textbf{d.}\\
Let A = \{1, 3\}, B = \{a, b, c\}, and C = \{x, y\}.\\
let f : A $\rightarrow$ B be defined as f = \{(1,a),(2,b)\} then it is not onto as it does not contain "c". Let g : B $\rightarrow$ C be defined as g = \{(a,x),(b,y),(c,y)\} then g $\circ$ f = \{(1,x),(2,y)\} which is onto.  \includegraphics[scale=0.70]{billeder/xzibit}\\

\textbf{e.}\\
We know that f is not one-to-one so there exists $a,b \in A$ with a and b being distinct values and $f(a) = f(b)$ therefore g $\circ$ f(a) = g(f(a)) = g(f(b)) = g $\circ$ f(b). This disproves that g $\circ$ f is one-to-one.\\

